package com.cat.graphTheory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-time-to-visit-disappearing-nodes/description/
 * @create 2025/9/23 21:38
 * @since JDK17
 */

public class Solution27 {
    public int[] minimumTime(int n, int[][] edges, int[] disappear) {
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        int[] ans = new int[n];
        for (int[] edge : edges) {  // 无向图
            g[edge[0]].add(new int[]{edge[1], edge[2]});
            g[edge[1]].add(new int[]{edge[0], edge[2]});
        }
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        Arrays.fill(ans, Integer.MAX_VALUE);
        heap.add(new int[]{0, 0});
        ans[0] = 0;
        while (!heap.isEmpty()) {
            var p = heap.poll();
            int dist = p[1];
            if (dist > ans[p[0]]) {
                continue;
            }
            for (var next : g[p[0]]) {
                if (dist + next[1] < ans[next[0]] && dist + next[1] < disappear[next[0]]) {
                    ans[next[0]] = dist + next[1];
                    heap.add(new int[]{next[0], dist + next[1]});
                }
            }
        }
        for (int i = 0; i < n; i++) {
            ans[i] = ans[i] == Integer.MAX_VALUE ? -1 : ans[i];
        }
        return ans;
    }
}
